Rotting oranges

Time: O(MxN); Space: O(MxN); easy

In a given grid, each cell can have one of three values: * the value 0 representing an empty cell; * the value 1 representing a fresh orange; * the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]

Output: -1

Explanation:

  • The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]

Output: 0

Explanation:

  • Since there are already no fresh oranges at minute 0, the answer is just 0.

Notes:

  • 1 <= len(grid) <= 10

  • 1 <= len(grid[0]) <= 10

  • grid[i][j] is only 0, 1, or 2.

[1]:

import collections

class Solution1(object):
    """
    Time:  O(m * n)
    Space: O(m * n)
    """
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        count = 0
        q = collections.deque()
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 2:
                    q.append((r, c, 0))
                elif val == 1:
                    count += 1

        result = 0
        while q:
            r, c, result = q.popleft()
            for d in directions:
                nr, nc = r + d[0], c + d[1]
                if not (0 <= nr < len(grid) and \
                        0 <= nc < len(grid[r])):
                    continue
                if grid[nr][nc] == 1:
                    count -= 1
                    grid[nr][nc] = 2
                    q.append((nr, nc, result+1))
        return result if count == 0 else -1

[2]:

s = Solution1()
grid = [[2,1,1],[1,1,0],[0,1,1]]
assert s.orangesRotting(grid) == 4
grid = [[2,1,1],[0,1,1],[1,0,1]]
assert s.orangesRotting(grid) == -1
grid = [[0,2]]
assert s.orangesRotting(grid) == 0